package heap.medium;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 丑数 II
 * 示例 1：
 *
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ugly-number-ii
 */
public class UglyNumberII_264 {

    public int nthUglyNumber(int n) {
        int[] arr = { 2, 3, 5};
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        set.add(1l);
        minHeap.offer(1l);
        for (int i = 1; i <= n; i++) {
            long poll = minHeap.poll();
            if (i == n)
                return (int)poll;
            for (int i1 : arr) {
                Long temp = i1 * poll;
                if (!set.contains(temp)){
                    set.add(temp);
                    minHeap.offer(temp);
                }
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        UglyNumberII_264 nu = new UglyNumberII_264();
        System.out.println(nu.nthUglyNumber(10));
    }
}
